import math
from collections import Counter

def _distance(x1, x2):
    """计算两个样本的欧氏距离（内部辅助函数）"""
    return math.sqrt(sum((a - b) **2 for a, b in zip(x1, x2)))

def knn_predict(sample, train_data, train_labels, k):
    """
    单个样本的k近邻预测
    参数:
        sample: 待预测样本（如[1.2, 3.4]）
        train_data: 训练样本列表（每个元素为样本）
        train_labels: 训练样本对应的标签列表
        k: 近邻数量（正整数）
    返回:
        预测标签
    """
    # 计算待预测样本与所有训练样本的距离
    distances = []
    for i in range(len(train_data)):
        dist = _distance(sample, train_data[i])
        distances.append((dist, train_labels[i]))  # 存储（距离，标签）元组
    
    # 按距离升序排序，取前k个近邻
    distances.sort()
    k_nearest_labels = [label for (_, label) in distances[:k]]
    
    # 多数表决：返回出现次数最多的标签
    return Counter(k_nearest_labels).most_common(1)[0][0]

def knn_classifier(test_data, train_data, train_labels, k=3):
    """
    k近邻分类器（批量预测）
    参数:
        test_data: 测试样本列表
        train_data: 训练样本列表
        train_labels: 训练样本标签列表
        k: 近邻数量（默认3）
    返回:
        测试样本的预测标签列表
    """
    # 输入合法性检查
    if len(train_data) != len(train_labels):
        raise ValueError("训练数据与标签数量不匹配")
    if k <= 0 or k > len(train_data):
        raise ValueError(f"k值必须为(0, {len(train_data)}]之间的整数")
    if not train_data:
        raise ValueError("训练数据不能为空")
    
    # 对每个测试样本进行预测
    predictions = [knn_predict(sample, train_data, train_labels, k) 
                  for sample in test_data]
    return predictions